/*
 * @lc app=leetcode id=211 lang=cpp
 *
 * [211] Add and Search Word - Data structure design
 */
class WordDictionary {
    class Trie {
        private:
            struct Node {
                Node** next;
                int cap;
                char val;
                bool mark;

                Node(char val, int cap=26) : val(val), mark(false), cap(cap) {
                    this->next = new Node*[cap]{NULL};
                }
            };
            Node *root;
        public:

            Trie() {
                root = new Node('\0');
            }

            void insert(string& s) {
                int idx = 0;
                Node *node = root;
                for (auto c : s) {
                    idx = c-'a';
                    if (!node->next[idx]) {
                        node->next[idx] = new Node(c);
                    }
                    node = node->next[idx];
                }
                node->mark = true;
            }

            bool searchFrom(string& s, int st, Node *node) {
                if (st == s.length()) {
                    return node->mark;
                }
                if (!node) {
                    return false;
                }
                Node *curr = NULL;
                char c = s[st];
                if (c == '.') {
                    for (int i=0; i<node->cap; i++) {
                        curr = node->next[i];
                        if (curr && searchFrom(s, st+1, curr)) {
                            return true;
                        }
                    }
                } else {
                    int idx = c - 'a';
                    curr = node->next[idx];
                    if (!curr) {
                        return false;
                    } else {
                        return searchFrom(s, st+1, curr);
                    }
                }
                return false;
            }

            bool search(string& s) {
                return searchFrom(s, 0, root);
            }
    };
public:
    Trie trie;
    /** Initialize your data structure here. */
    WordDictionary() {
        
    }
    
    /** Adds a word into the data structure. */
    void addWord(string word) {
        trie.insert(word);
        
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    bool search(string word) {
        return trie.search(word);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

